package tianhao.luo.algorithm;

import java.util.*;

/**
 * 贪心算法
 * @author: tianhao.luo@hand-china.com 2021/7/2  22:10
 */
public class GreedyAlgorithm {

    /**
     * 广播
     */
    private HashMap<String, Set<String>> broadcasts;

    public GreedyAlgorithm(HashMap<String, Set<String>> broadcasts) {
        this.broadcasts = broadcasts;
    }

    public void get(){
        // 存放所有地区
        Set<String> allAreas = new HashSet<>();
        for (Map.Entry<String, Set<String>> entry : broadcasts.entrySet()) {
            allAreas.addAll(entry.getValue());
        }
        // 创建一个ArrayList,存放选择的电台集合
        List<String> selects = new ArrayList<>();
        // 定义一个临时的集合,在遍历过程中,存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
        Set<String> temp = new HashSet<>();
        // 定义一个maxKey,保存在一次遍历过程中,能够覆盖的最多未覆盖的地区对应得电台得key
        // 如果maxKey不为空,则会加入selects中
        String maxkey = null;
        while (allAreas.size() >0){
            // 每进行一次循环,需要将maxKey置为null
            maxkey =null;
            // allAreas不为0,则表示还没有覆盖到所有地区
            for (Map.Entry<String, Set<String>> entry : broadcasts.entrySet()) {
                /// 每进行一次for,需要清除
                temp.clear();
                temp.addAll(entry.getValue());
                // 求出tempSet和allAreas集合得交集,交集会赋给temp
                temp.retainAll(allAreas);
                // 如果当前这个集合包含的未覆盖地区的数量(temp),比maxKey指向的集合地区还多,就需要重置maxKey
                // (maxkey == null || temp.size()>broadcasts.get(maxkey).size())体现了贪心算法
                if (temp.size()>0 && (maxkey == null || temp.size()>broadcasts.get(maxkey).size())){
                    maxkey =entry.getKey();
                }
            }
            // maxKey !=null,就应该吧maxKey加入selects
            if (maxkey !=null){
                selects.add(maxkey);
                // 将maxKey指向的广播电台的地区从allAreas中清除掉
                allAreas.removeAll(broadcasts.get(maxkey));
            }
        }

        System.out.println("得到的结果:"+selects);
    }
}
